package arithmetic.leetCode;

import arithmetic.geektime.tree.TreeNode;
import arithmetic.geektime.tree.TreeTraverse;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Stack;

/**
 * @author dycong
 * @date 2019/11/21 9:34
 */
public class TreeInorderTraversal_94 {

    public static void main(String[] args) {
        TreeTraverse.TreeHelper treeHelper = new TreeTraverse.TreeHelper();
        TreeNode root = treeHelper.getTree(5);
        TreeInorderTraversal_94 twoSum_1 = new TreeInorderTraversal_94();
        System.out.println(twoSum_1.inorderTraversal(root));
        System.out.println(twoSum_1.inorderTraversal_2(root));
    }

    /**
     * /*
     * 1
     * / \
     * 2   3
     * / \   \
     * 4   5   6
     * 层次遍历顺序：[1 2 3 4 5 6]
     * 前序遍历顺序：[1 2 4 5 3 6]
     * 中序遍历顺序：[4 2 5 1 3 6]
     * 后序遍历顺序：[4 5 2 6 3 1]
     * <p>
     * left - right - root
     *
     * @param root
     * @return
     */
    public List<Integer> inorderTraversal(TreeNode root) {
        if (root == null) return Collections.emptyList();

        List<Integer> ret = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;

        while (cur!=null || !stack.isEmpty()) {
            //当前节点的左节点全部入栈
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            //后入先出一个
            TreeNode node = stack.pop();
            ret.add(node.val);
            //处理右节点，若有右子节点会在下一while周期，将其全部左节点入栈
            cur = node.right;
        }
        return ret;
    }

    public List<Integer> inorderTraversal_2(TreeNode root) {
        if (root == null) return Collections.emptyList();
        List<Integer> ret = new ArrayList<>();

        return postOrder(root, ret);
    }


    /**
     * 递归中序遍历
     *
     * @param root
     * @param ret
     * @return
     */
    public List<Integer> postOrder(TreeNode root, List<Integer> ret) {
        if (root == null) return ret;

        postOrder(root.left, ret);
        ret.add(root.val);
        postOrder(root.right, ret);

        return ret;
    }


}
